1715B - Beautiful Array - CodeForces Solution


constructive algorithms greedy math

Please click on ads to support us..

Python Code:

for _ in range(int(input())):
    n,k,b,s = map(int,input().split())
    res = [0] * n
    res[0] = k * b
    s = s -k * b
    num = 0
    while num < n and s >= 0:
        temp = min(k-1,s)
        s -= temp

        res[num] += temp
        num += 1
    if s != 0:
        print("-1")
    else:
        print(*res)

C++ Code:

#include <bits/stdc++.h>
using namespace std;

#define IOS                \
  ios::sync_with_stdio(0); \
  cin.tie(0);              \
  cout.tie(0);
#define int long long int

#define vi vector<int>
#define pii pair<int, int>
#define vpii vector<pii>
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define exit exit(0)
typedef long long ll;
#define double long double
#define debug1(x) cerr << #x << ": " << x << endl
#define debug2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl
#define all(a) a.begin(), a.end()

void solve()
{
int n,k,m,s;
cin>>n>>k>>m>>s;

if(s < k*m or s > k*m + n*(k-1))
{
    cout << -1 << endl;
    return;
}
vector<int> res(n);
res[0] = m*k;
s -= m*k;
if(s>0)
{
    res[0] += min(k-1,s);
    s -= min(k-1,s);
}
for(int i=1; i<n; i++)
{
    if(s >= k-1)
    {
    res[i] = min(s,k-1);
        s-=k-1;
    }else {
         res[i] = min(s,k-1);
         s = 0;
    }

}
for(auto x: res)
{
    cout << x << " ";
}
cout << endl;
}

int32_t main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}


Comments

Submit
0 Comments
More Questions

1302. Deepest Leaves Sum
1209. Remove All Adjacent Duplicates in String II
994. Rotting Oranges
983. Minimum Cost For Tickets
973. K Closest Points to Origin
969. Pancake Sorting
967. Numbers With Same Consecutive Differences
957. Prison Cells After N Days
946. Validate Stack Sequences
921. Minimum Add to Make Parentheses Valid
881. Boats to Save People
497. Random Point in Non-overlapping Rectangles
528. Random Pick with Weight
470. Implement Rand10() Using Rand7()
866. Prime Palindrome
1516A - Tit for Tat
622. Design Circular Queue
814. Binary Tree Pruning
791. Custom Sort String
787. Cheapest Flights Within K Stops
779. K-th Symbol in Grammar
701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST